kw.\*:("Dérandomisation")
Results 1 to 25 of 55
Selection :
Derandomization that is rarely wrong from short advice that is typically goodGOLDREICH, Oded; WIGDERSON, Avi.Lecture notes in computer science. 2002, pp 209-223, issn 0302-9743, isbn 3-540-44147-6, 15 p.Conference Paper
Antirandomizing the wrong gameDOERR, Benjamin.Lecture notes in computer science. 2002, pp 876-887, issn 0302-9743, isbn 3-540-43864-5, 12 p.Conference Paper
On the derandomization of constant depth circuitsKLIVANS, Adam R.Lecture notes in computer science. 2001, pp 249-260, issn 0302-9743, isbn 3-540-42470-9Conference Paper
Improved derandomization of BPP using a hitting set generatorGOLDREICH, O; WIGDERSON, A.Lecture notes in computer science. 1999, pp 131-137, issn 0302-9743, isbn 3-540-66329-0Conference Paper
Hardness hypotheses, derandomization, and circuit complexityHITCHCOCK, John M; PAVAN, A.Lecture notes in computer science. 2004, pp 336-347, issn 0302-9743, isbn 3-540-24058-6, 12 p.Conference Paper
When worlds collide: Derandomization, lower bounds, and Kolmogorov complexityALLENDER, Eric.Lecture notes in computer science. 2001, pp 1-15, issn 0302-9743, isbn 3-540-43002-4Conference Paper
A 3-approximation algorithm for the k-level uncapacitated facility location problemAARDAL, K; CHUDAK, F. A; SHMOYS, D. B et al.Information processing letters. 1999, Vol 72, Num 5-6, pp 161-167, issn 0020-0190Article
A zero-one law for RP and derandomization of AM if NP is not smallIMPAGLIAZZO, Russell; MOSER, Philippe.Information and computation (Print). 2009, Vol 207, Num 7, pp 787-792, issn 0890-5401, 6 p.Article
Derandomization of PPSZ for unique-k-SATROLF, Daniel.Lecture notes in computer science. 2005, pp 216-225, issn 0302-9743, isbn 3-540-26276-8, 10 p.Conference Paper
The first-order isomorphism theoremAGRAWAL, Manindra.Lecture notes in computer science. 2001, pp 70-82, issn 0302-9743, isbn 3-540-43002-4Conference Paper
Deterministic dictionariesHAGERUP, Torben; MILTERSEN, Peter Bro; PAGH, Rasmus et al.Journal of algorithms (Print). 2001, Vol 41, Num 1, pp 69-85, issn 0196-6774Article
Expected complexity of graph partitioning problemsKUCERA, L.Discrete applied mathematics. 1995, Vol 57, Num 2-3, pp 193-212, issn 0166-218XConference Paper
Weighted fractional and integral k-matching in hypergraphsSRIVASTAV, A; STANGIER, P.Discrete applied mathematics. 1995, Vol 57, Num 2-3, pp 255-269, issn 0166-218XConference Paper
Relations between average-case and worst-case complexityPAVAN, A; VINODCHANDRAN, N. V.Lecture notes in computer science. 2005, pp 422-432, issn 0302-9743, isbn 3-540-28193-2, 11 p.Conference Paper
Solvable group isomorphism is (almost) in NP ∩ coNPARVIND, V; TORAN, Jacobo.IEEE Conference on Computational Complexity. 2004, pp 91-103, isbn 0-7695-2120-7, 1Vol, 13 p.Conference Paper
A simpler and better derandomization of an approximation algorithm for single source rent-or-buyWILLIAMSON, David P; VAN ZUYLEN, Anke.Operations research letters. 2007, Vol 35, Num 6, pp 707-712, issn 0167-6377, 6 p.Article
Some results on derandomizationBUHRMAN, Harry; FORTNOW, Lance; PAVAN, A et al.Lecture notes in computer science. 2003, pp 212-222, issn 0302-9743, isbn 3-540-00623-0, 11 p.Conference Paper
Solving some discrepancy problems in NCMAHAJAN, S; RAMOS, E. A; SUBRAHMANYAM, K. V et al.Algorithmica. 2001, Vol 29, Num 3, pp 371-395, issn 0178-4617Article
The zero-one law holds for BPPVAN MELKEBEEK, D.Theoretical computer science. 2000, Vol 244, Num 1-2, pp 283-288, issn 0304-3975Article
Small-bias probability spaces: efficient constructions and applicationsNAOR, J; NAOR, M.SIAM journal on computing (Print). 1993, Vol 22, Num 4, pp 838-856, issn 0097-5397Article
A zero-one SUBEXP-dimension law for BPPMOSER, Philippe.Information processing letters. 2011, Vol 111, Num 9, pp 429-432, issn 0020-0190, 4 p.Article
Derandomizing homomorhism testing in general groupsSHPILKA, Amir; WIGDERSON, Avi.SIAM journal on computing (Print). 2007, Vol 36, Num 4, pp 1215-1230, issn 0097-5397, 16 p.Article
Efficient steganography with provable security guaranteesKIAYIAS, Aggelos; RAEKOW, Yona; RUSSELL, Alexander et al.Lecture notes in computer science. 2005, pp 118-130, issn 0302-9743, isbn 3-540-29039-7, 1Vol, 13 p.Conference Paper
A note on approximate counting for k-DNFTREVISAN, Luca.Lecture notes in computer science. 2004, pp 417-425, issn 0302-9743, isbn 3-540-22894-2, 9 p.Conference Paper
Small pseudo-random families of matrices: Derandomizing approximate quantum encryptionAMBAINIS, Andris; SMITH, Adam.Lecture notes in computer science. 2004, pp 249-260, issn 0302-9743, isbn 3-540-22894-2, 12 p.Conference Paper